МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
Дослідження методів багатопараметричної оптимізації на прикладі методів прямого пошуку
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 4
з курсу “Методи синтезу та оптимізації”
для студентів базового напряму 6.08.04 “Компютерні науки”
ЗАТВЕРДЖЕНО
На засіданні кафедри САПР
Протокол № 1 від 28.08. 2008 р.
ЛЬВІВ 2008
Дослідження методів багатопараметричної оптимізації на прикладі методів прямого пошуку. Методичні вказівки до лабораторної роботи № 4 з курсу “Методи синтезу та оптимізації” для студентів базового напряму 6.08.04 “Компютерні науки” /Укл. Теслюк В. М., Андрійчук М. І. – Львів: НУ “ЛП”, 2008 р.
Укладачі: Теслюк Василь Миколайович, к.т. н., доцент; Андрійчук Михайло Іванович, к. ф.-м. в., доцент.
Відповідальний за випуск: Ткаченко С. П., к.т. н., доцент
Рецензенти: Каркульовський В. І., к.т. н., доцент,
Стех Ю. В., к.т. н., доцент
1. МЕТА РОБОТИ
Вивчити основні методи багатопараметричної оптимізації на основі алгоритмів прямого пошуку
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Прямі методи
Прямі методи, або методи нульового порядку не вимагають знання цільової функції в явному вигляді. Вони не вимагають регулярності і неперервності цільової функції й існування похідних. Це є істотною перевагою при розв’язуванні складних технічних і економічних задач. При реалізації прямих методів істотно скорочується етап підготовки рішення задачі, тому що немає необхідності у визначенні перших і других похідних. Прямі методи в основному носять евристичний характер. До прямих методів відноситься цілий ряд алгоритмів, що відрізняються по своїй ефективності. Методи призначені для рішення безумовних задач оптимізації
.
Алгоритм Гауса
Це найпростіший алгоритм, що полягає в тому, що на кожному кроці (кожній ітерації) мінімізація здійснюється тільки по одній компоненті вектора змінних .
Нехай нам дане початкове наближення . На першій ітерації знаходимо значення мінімуму функції при першій координаті, що змінюється, і фіксованих інших, тобто
.
Рис. 1.
У результаті одержуємо нову точку . Далі з точки шукаємо мінімум функції, змінюючи другу координату і вважаючи фіксованими всі інші координати. У результаті одержуємо значення
і нову точку . Продовжуючи процес, після кроків одержуємо точку , починаючи з якої процес відновлюється.
Як умови припинення пошуку можна використовувати наступні два критерії:
.
, .
Метод дуже простий, але не дуже ефективний. Проблеми можуть виникнути, коли лінії рівня сильно витягнуті і "еліпсоїди" орієнтовані, наприклад, уздовж прямих виду . У подібній ситуації пошук швидко застряє на дні такого яру, а якщо початкове наближення виявляється на осі "еліпсоїда", то процес так і залишиться в цій точці.
Найбільш прийнятні результати виходять у тих випадках, коли цільова функція являє собою опуклу сепарабельну функцію виду
.
Метод пошуку по симплексу ( метод)
Робота симплексного методу починається з побудови регулярного симплекса в просторі незалежних змінних і оцінювання цільової функції в кожній з вершин симплекса. При цьому визначається вершина, якій відповідає найбільше значення цільвої функції.
а б
Рис. 2. Побудова нового симплекса.
а – початковий симплекс ; б – новий симплекс .
Після цього знайдена вершина проектується через центр ваги інших вершин симплекса в нову точку, яка використовується як вершина нового симплекса. Якщо функція спадає достатньо плавно, ітерації продовжуються доти, поки або не буде накрита точка мінімуму, або не почнеться циклічний рух по двох чи більше симплексах. В таких ситуаціях можна скористатись наступними трьома правилими.
Правило 1. “Накриття” точки мінімуму.
Якщо вершина, якій відповідає найбільше значення цільової функції, побудована на попередній ітерації, то замість неї береться вершина, якій відповідає наступне по величині значення цільової функції.
Правило 2. Циклічний рух.
Якщо деяка вершина симплекса не виключається на протязі більше...
